---
title: "8、扫雷"
created: 2025-11-28
tags:
  - 算法
---

# 8、扫雷

## 题目 [扫雷](https://www.lanqiao.cn/paper/3822/problem/549/)

![[image-ff180cc7.png]]

## 思路分析

本来想用前缀和 但是边边角角无法框出3\*3的范围

好像也行 在外层都加上一层0

![[image-36bf3152.png]]

不对 也不行 二维前缀和是以某点为右下角确定的一个矩阵 只能统计到其左上角的数量

只能暴力吗 暂时没想到好的方法 先暴力把一半分拿下吧

暴力的话发现 还是在最外层加上一圈0比较方便

然后从1,1枚举到n,n 对每个点进行检查 若该点是1 就直接标记为9 若不是1 就分别从左右上下左上左下右上右下8个方向检查……嘶 还是得想办法把一个区域的总和快速算出来
这样实在太麻烦了

好像又能用前缀和…… 对某个点来说 看以它为中心的3\*3的方格的总和 可以用它右下角的点的二维前缀和求出来

![[image-603624a2.png]]

具体来说 把它右下角的点当做x1,y1，左上角的点当成x2,y2

那么这个3\*3的窗口的总和就是 $s[x1,y1]-s[x1,y2-1]-s[x2-1,y1]+s[x2-1,y2-1]$

![[image-12e49c19.png]]

边界情况也适用

所以应该是可行的

那么就是 对于每个点i,j 看该点是是不是1 不是1 就拿i+1,j+1和i-1,j-1做二维前缀和的求值

现在就是考虑 怎么在最外层加上一圈0 左上加0可以直接从1开始读入 但是右下的话

要怎么做 其实本身就是0 读入的时候从1读到n,m 用的时候n,m放大一个用就行了

注意的是 构造前缀和的时候 要把n+1,m+1也构造进去

还以为只能拿一半 没想到这题就一个案例……直接20分到手了 啊这 这也太……

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=110;

int a[N][N],s[N][N],ans[N][N];

int main()

{

	int n,m;

	cin>>n>>m;

	for(int i=1;i<=n;i++)

		for(int j=1;j<=m;j++)

			cin>>a[i][j];

	n++,m++;

	for(int i=1;i<=n;i++)

		for(int j=1;j<=m;j++)

			s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];

	for(int i=1;i<n;i++){

		for(int j=1;j<m;j++){

			if(a[i][j]==1)

				ans[i][j]=9;

			else           //x2,y2      x2,y1-1        x1-1,y2      x1-1,y1-1

				ans[i][j]=s[i+1][j+1]-s[i+1][j-1-1]-s[i-1-1][j+1]+s[i-1-1][j-1-1];

		}

	}

	for(int i=1;i<n;i++){

		for(int j=1;j<m;j++){

			cout<<ans[i][j]<<" ";

		}

		cout<<endl;

	}

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[7、积木画|7、积木画]] 🏠 [[00-刷题理模型]] ➡️ [[9、李白打酒加强版|9、李白打酒加强版]]